In some array arr, the values were in arithmetic progression: the values arr[i + 1] - arr[i] are all equal for every 0 <= i < arr.length - 1.
A value from arr was removed that was not the first or last value in the array.
Given arr, return the removed value.
Example 1:
Input: arr = [5,7,11,13] Output: 9 Explanation: The previous array was [5,7,9,11,13].
Example 2:
Input: arr = [15,13,12] Output: 14 Explanation: The previous array was [15,14,13,12].
Constraints:
3 <= arr.length <= 10000 <= arr[i] <= 105- The given array is guaranteed to be a valid array.
Average Rating: 4.94 (17 votes)
Video Solution
Solution Article
Approach 1: Linear search
Intuition
Let's try to find the missing number by linearly scanning the array from start to end. Since we are given that the first and the last numbers cannot be removed, we can use them to get the required difference between each pair of consecutive elements.
difference=number of valueslast value−first value
Once we have the difference we can use it to know what the value at each index is supposed to be. Using the difference as calculated above, and defining initial to be the value at index 0, we have the following:
index 0=initialindex 1=initial+differenceindex 2=initial+2⋅differenceindex 3=initial+3⋅difference…index n=initial+n⋅difference
Let's use this to figure out the first missing value in the Arithmetic Progression.
Algorithm
- Get the value of
differenceusing first and the last element,difference = last_value - first_value / number_of_values. - Start with the first element as expected value
expected = first_element - Run a loop from the first value to the last while checking if the current value is equal to
expected. If it is not, then increaseexpectedbydifferencefor the next iteration. - Return the first
expectedvalue that doesn't match value in the array`.
Complexity Analysis
-
Time complexity : O(n). Where n is the length of array
arrsince in the worst case we iterate over the entire array. -
Space complexity : O(1). Algorithm requires constant space to execute.
Approach 2: Binary Search
Intuition
In the previous approach we saw that we can get the value required at any index. Let's try to use that property to binary search for the missing value.
We know that there is only one missing number in the given progression. At any index i we can figure out if the value at index i is at the correct position by adding difference times i to the first value in the list, and then comparing it with the value at index i. if they match it means the missing value is in an index on the right of i else it's on the left of i or at i.
This fact can be used to find the index which has the first incorrect number using binary search because if i is the first index with an incorrect number all indices following i would be at incorrect positions (they should be present at 1 position further, since one number is missing) and all numbers before index i will be at correct position. This property is required for binary search to be possible.
Algorithm
- Get the value of
differenceusing first and the last element,difference = last_value - first_value / number_of_values. - Start with left index
lo = 0and right indexhi = arr.size() - 1. - Pick a mid point index
mid = (lo + hi) / 2. - If
arr[mid] == first_element + mid * difference. Binary search on the right ofmidelse binary search on left side ofmidincludingmiditself. - End when there is a single index left as this would be the first index with incorrect value.
- Return the value supposed to be at this index which would be
first_element + difference * index.
Complexity Analysis
-
Time complexity : O(logn).Where n is the length of array
arrsince we cut the search space in half at every iteration. -
Space complexity : O(1). Algorithm requires constant space to execute.
Last Edit: April 29, 2021 7:57 AM
Python one line solution:
Using the sum of the arithmetic progression
class Solution:
def missingNumber(self, arr: List[int]) -> int:
return int((arr[0] + arr[-1])/2 * (len(arr)+1) - sum(arr))
April 23, 2021 6:00 AM
lol. anything to do with binary search or derivation should medium level problem IMHO.
I have not thought about binary search approach. Really an eye-opening solution. So thumb rule is "if array is sorted, then better time complexity is O(log n)"
If think int overflow for binary search (with Java and C++) needs to be addressed when getting the mid. Shouldn't it be lo + (hi - lo)//2? In python, it doesn't matter I think?
Easiest solution:
int missingNumber(vector<int>& arr) {
int k = arr[1] - arr[0];
int k2 = arr[2] - arr[1];
if(k > 0 && k > k2) swap(k, k2);
if(k < 0 && k < k2) swap(k, k2);
for(int i = 0; i + 1 < arr.size(); i++) {
if(arr[i + 1] - arr[i] != k) return arr[i] + k;
}
return arr[0];
}
You don't have any submissions yet.
xxxxxxxxxxclass Solution {public: int missingNumber(vector<int>& arr) { }};